﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _14.QuickSort
{
    class QuickSortAlgo
    {
        static List<int> QuickSort(List<int> array)
        {
            if (array.Count <= 1)
            {
                return array;
            }
            int pivot = array[array.Count / 2];
            List<int> left = new List<int>();
            List<int> right = new List<int>();
            for (int i = 0; i < array.Count; i++)
            {
                if (i != (array.Count / 2))
                {
                    if (array[i] <= pivot)
                    {
                        left.Add(array[i]);
                    }
                    else
                    {
                        right.Add(array[i]);
                    }
                }
            }
            return Concatenate(QuickSort(left), pivot, QuickSort(right));
        }
        static List<int> Concatenate(List<int> left, int pivot, List<int> right)
        {
            List<int> result = new List<int>();

            foreach (int item in left)
            {
                result.Add(item);
            }
            result.Add(pivot);
            foreach (int item in right)
            {
                result.Add(item);
            }
            return result;
        }
        static void Main(string[] args)
        {
            List<int> unsorted = new List<int> { 3, 4, 7, 2, 18, 1, 15 };
            Console.WriteLine("Unsorted Array:{0}", String.Join(" ", unsorted));
            List<int> sorted = QuickSort(unsorted);
            Console.WriteLine("Sorted Array:{0}", String.Join(" ", sorted));
        }
    }
}
